package slidingwindow;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//串联所有单词的⼦串
public class FindSubstring {
    public static void main(String[] args) {
        String s = "aaaaaaaaaaaaaa";
        String[] words = {"aa", "aa"};
        System.out.println(findSubstring(s, words));
    }

    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<Integer>();
        Map<String, Integer> hash1 = new HashMap<String, Integer>();
        for (String str : words) hash1.put(str, hash1.getOrDefault(str, 0) + 1);
        int len = words[0].length(), m = words.length;

        for (int i = 0; i < len; i++) {
            Map<String, Integer> hash2 = new HashMap<String, Integer>();
            for (int right = i, left = i, count = 0; right + len <= s.length(); right += len) {
                String in = s.substring(right, right + len);
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                if (hash2.get(in) <= hash1.getOrDefault(in, 0)) count++;

                //判断
                if (right - left + 1 > len * m) {
                    String out = s.substring(left, left + len);
                    if (hash2.get(out) <= hash1.getOrDefault(out, 0)) count--;
                    hash2.put(out, hash2.get(out) - 1);
                    left += len;
                }
                if (count == m) ret.add(left);

            }
        }
        return ret;
    }


//
//    public static List<Integer> findSubstring(String s, String[] words) {
//        List<Integer> ret = new ArrayList<Integer>();
//
//        Map<String,Integer> hash1 = new HashMap<String, Integer>();//保存字典中单词出现的频次
//        for (String str : words) hash1.put(str,hash1.getOrDefault(str,0)+1);
//        int len = words[0].length(),m = words.length;
//        for (int i = 0; i < len; i++) {
//            Map<String,Integer> hash2 = new HashMap<String, Integer>();//保存窗口内所有单词的频次
//
//            for (int left = i,right = i, count = 0; right + len <= s.length(); right += len) {
//                //进窗口
//                String in = s.substring(right,right + len);
//                hash2.put(in,hash2.getOrDefault(in,0)+1);
//                //if(hash2.get(in) <= hash1.get(in)) count++;  //hash1.get(in)可能会没有，没有的话会报错
//                if(hash2.get(in) <= hash1.getOrDefault(in,0)) count++;
//                //判断
//                if(right - left + 1 > len * m) {
//                    //出窗口
//                    String out = s.substring(left, left+len);
//                    if(hash2.get(out) <= hash1.getOrDefault(out,0)) count--;
//                    hash2.put(out,hash2.get(out) - 1);
//                    left += len;
//                }
//                //更新结果
//                if(count == m) ret.add(left);
//
//            }
//        }
//        return ret;
//    }
}
